function Point(x, y, val) {
  this.x = x;
  this.y = y;
  this.val = val;
}

/**
 * @param {number[][]} heights
 * @return {number}
 */
var minimumEffortPath = function (heights) {
  // 方向, 用于坐标上下左右的移动
  let direction = [
    [1, 0],
    [0, 1],
    [0, -1],
    [-1, 0]
  ];
  let m = heights.length, n = heights[0].length;
  function bfs(mid) {
    // 用于判断某个位置是否已经访问/展开过
    let visited = new Array(m);
    for (let i = 0; i < m; i++) {
      visited[i] = new Array(n).fill(false);
    }
    let queue = [new Point(0, 0)];
    visited[0][0] = true;
    while(queue.length) {
      let x = queue[0].x, y = queue[0].y;
      queue.splice(0, 1);
      if(x == heights.length - 1 && y == heights[0].length - 1) {
        return true;
      }
      for(let i = 0; i < 4; i++) {
        let newX = x + direction[i][0];
        let newY = y + direction[i][1];
        if(newX < m && newX >= 0 && newY < n && newY >= 0 && !visited[newX][newY] && Math.abs(heights[x][y] - heights[newX][newY]) <= mid) {
          visited[newX][newY] = true;
          queue.push(new Point(newX, newY));
        }
      }
    }
    return false;
  }
  let left = 0,
    right = 1000000;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (bfs(mid, heights)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return right;
};
let heights = [
  [1, 2, 2],
  [3, 8, 2],
  [5, 3, 5]
];
console.log(minimumEffortPath(heights));
heights = [
  [1, 2, 3],
  [3, 8, 4],
  [5, 3, 5]
];
console.log(minimumEffortPath(heights));
heights = [
  [1, 2, 1, 1, 1],
  [1, 2, 1, 2, 1],
  [1, 2, 1, 2, 1],
  [1, 2, 1, 2, 1],
  [1, 1, 1, 2, 1]
];
console.log(minimumEffortPath(heights));
